package main

import (
	"bytes"
	"fmt"
)

// 位向量
/*
与位图存储不同之处在于，位向量注重偏移量和存储索引
　　例如如何利用位向量向集合中插入值呢？
例如32位uint 型来存储154 在位向量中表示如下
索引：index = 154/32 =4
偏移：offset = 154%32 = 26
编译表示 （1<<26）
切片中表示 []uint32{0,0,0,0,uint32(1<<26)}
　　如何利用位向量判断值A是否存在呢？
　　1. 值A的索引要存在，例如在位向量中，集合中最大值的索引之后是没有存储变量的，所以也要对A分割出索引index和偏移offset，如果index>集合长度，则认为不存在
　　2. 判断了索引还需要判断片偏移，将1<<offset的结果与索引位上的值逐位相&（与），若为1则集合中存在
*/
type IntSet struct {
	words []uint64
}

func (s *IntSet) Has(x int) bool {
	word, bit := x/64, uint(x%64)
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

func (s *IntSet) Add(x int) {
	word, bit := x/64, uint(x%64)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}
func (s *IntSet) UnionWith(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] |= tword
		} else {
			s.words = append(s.words, tword)
		}
	}
}

func (s *IntSet) String() string {
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			// 只有 有这个值 才会不等于0
			if word&(1<<uint64(j)) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte(' ')
				}
				fmt.Fprintf(&buf, "%d", 64*i+j)
			}
		}
	}

	buf.WriteByte('}')
	return buf.String()
}

func main() {
	uSet := IntSet{}
	uSet.Add(3)
	uSet.Add(1)
	println(uSet.Has(1))
	println(uSet.String())
	fmt.Println()
}
